package gold.digger;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC174 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 不怪自己笨，只怪题目太狡猾
     * @return:
     */
    class Solution {

        public int calculateMinimumHP(int[][] dungeon) {
            int n = dungeon.length, m = dungeon[0].length;
            int[][] dp = new int[n + 1][m + 1];
            //初始化
            for (int i = 0; i <= n; ++i) {
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }
            dp[n][m - 1] = dp[n - 1][m] = 1;
            //右下向左上遍历
            for (int i = n - 1; i >= 0; --i) {
                for (int j = m - 1; j >= 0; --j) {
                    int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
                    dp[i][j] = Math.max(minn - dungeon[i][j], 1);
                }
            }

            return dp[0][0];
        }

        public int calculateMinimumHP_Fail(int[][] dungeon) {
            if (null == dungeon || dungeon.length <= 0) return 0;
            int m = dungeon.length, n = dungeon[0].length;
            int[][] dp = new int[m][n];
            int[][] posX = new int[m][n];
            int[][] posY = new int[m][n];

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }

            dp[0][0] = 1 - dungeon[0][0] > 0 ? 1 - dungeon[0][0] : dungeon[0][0];
            for (int i = 1; i < m; i++) {
                dp[i][0] = dp[i - 1][0] - dungeon[i][0];
                posX[i][0] = i - 1;
                posY[i][0] = 0;
            }
            for (int j = 1; j < n; j++) {
                dp[0][j] = dp[0][j - 1] - dungeon[0][j];
                posX[0][j] = 0;
                posY[0][j] = j - 1;
            }

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (dp[i - 1][j] < dp[i][j - 1]) {
                        dp[i][j] = dp[i - 1][j];
                        posX[i][j] = i - 1;
                        posY[i][j] = j;
                    } else {
                        dp[i][j] = dp[i][j - 1];
                        posX[i][j] = i;
                        posY[i][j] = j - 1;
                    }

                    dp[i][j] -= dungeon[i][j];
                }
            }

            int curMax = Integer.MIN_VALUE;
            int x = m - 1, y = n - 1;
            while (!(x == 0 && y == 0)) {
                curMax = Math.max(dp[x][y], dp[posX[x][y]][posY[x][y]]);
                int tempX = posX[x][y];
                y = posY[x][y];
                x = tempX;
            }

            return curMax;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = {{-2, -3, 3}, {-5, -10, 1}, {20, 30, -5}};
        System.out.println(solution.calculateMinimumHP(arr));
    }

    public static void main(String[] args) throws Exception {
        LC174 an = new LC174();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
